package com.cty._01_Base._10_Fibonacci;

/**
 * @Auther: cty
 * @Date: 2020/7/1 11:30
 * @Description: 面试题10：斐波那契数列
 *               题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
 * @version: 1.0
 */
public class Fibonacci {
    /**
     * 递归实现斐波那契数列
     * @param n
     * @return
     */
    public static long recFibonacci(int n){
        if(n <= 0)
            return 0;

        if(n == 1)
            return 1;

        return recFibonacci(n-1) + recFibonacci(n-2);
    }  // end recFibonacci()

    /**
     * 循环实现斐波那契数列
     * @param n
     * @return
     */
    public static long cirFibonacci(int n){
        int[] result = {0, 1};
        if(n < 2)
            return result[n];

        long FibN = 0;
        long FibNMinusOne = 1;
        long FibNMinusTwo = 0;
        for(int i=2; i<=n; i++){
            FibN = FibNMinusOne + FibNMinusTwo;

            FibNMinusTwo = FibNMinusOne;
            FibNMinusOne = FibN;
        }
        return FibN;
    }  // end circleFibonacci()

}  // end class
